package com.fosss.krusikal;

import com.sun.javafx.geom.Edge;

import java.util.Arrays;

/**
 * 克鲁斯卡尔算法
 */
public class Kruskal {
    private int edgeNum;//边的数量
    private char[] vertexs;//顶点数组
    private int[][] matrix;//邻接矩阵
    //INF表示一个足够大的数，用来代表顶点间不连通
    public static final int INF=Integer.MAX_VALUE;

    /**
     * 构造方法
     */
    public Kruskal(char[] vertexs,int[][] matrix){
        int length = vertexs.length;

        this.vertexs=vertexs;
        this.matrix = matrix;

        //求出边的数量
        for (int i = 0; i < length; i++) {
            for (int j = i+1; j < length; j++) {
                if(matrix[i][j]<INF){
                    edgeNum++;
                }
            }
        }

    }

    /**
     * 打印邻接矩阵
     */
    public void print(){
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                System.out.printf("%-12d",matrix[i][j]);
            }
            System.out.println();
        }
    }

    /**
     * 将邻接矩阵转化为点对点的边的形式
     */

    public EData[] getEdges(){
        EData[] edges=new EData[edgeNum];
        int index=0;
        for(int i = 0; i < vertexs.length; i++){
            for (int j=i+1;j< vertexs.length;j++){
                if(matrix[i][j]!=0&&matrix[i][j] != INF){
                    edges[index]=new EData(vertexs[i],vertexs[j],matrix[i][j]);
                    index++;
                }
            }
        }
        return edges;
    }

    /**
     * 将获取的边按照长度从小到大排序-冒泡排序
     */
    public void sortEdges(EData[] edges){
        for(int i=0;i<edgeNum-1;i++){
            for(int j = 0; j < edgeNum-1-i; j++){
                if(edges[j].getWeight()>edges[j+1].getWeight()){
                    EData temp=null;
                    temp=edges[j];
                    edges[j]=edges[j+1];
                    edges[j+1]=temp;
                }
            }
        }
    }

    /**
     * 获取某顶点的下标
     */
    private int getPosition(char c){
        for (int i=0;i<vertexs.length; i++){
            if(vertexs[i]==c){
                return i;
            }
        }
        //找不到返回-1
        return - 1;
    }

    /**
     * 获取下标为i的顶点的终点！！！！！！
     * @param ends 这个数组记录了各个顶点对应的终点是什么，是在遍历的过程中逐步形成的
     */
    public int getEnd(int[] ends,int i){
        while (ends[i]!=0){
            i=ends[i];
        }
        return i;
    }

    /**
     * 编写克鲁斯算法的具体实现
     */
    public void kruskalGo(){
        //用来储存最后的最小生成树
        EData[] result=new EData[vertexs.length-1];//最后的边的个数为顶点个数-1

        //储存顶点的终点
        int[] ends=new int[edgeNum];

        //结果数组的下标
        int index=0;

        //获取边
        EData[] edges = getEdges();
        System.out.println(Arrays.toString(edges));
        //进行排序
        sortEdges(edges);

        for(int i=0;i<edgeNum; i++){

            //获取每条边的两端
            char start = edges[i].getStart();
            char end = edges[i].getEnd();

            //获取两端的下标
            int p1 = getPosition(start);
            int p2 = getPosition(end);

            //获取两端的终点
            int end1 = getEnd(ends, p1);
            int end2 = getEnd(ends, p2);

            //判断终点是否相同，如果相同，则为回路
            if(end1!=end2){
                //不构成回路，则设置该顶点的终点
                ends[end1]=end2;
                result[index]=edges[i];
                index++;
//                System.out.println(edges[i]);
            }
        }
        System.out.println(Arrays.toString(result));
    }


}















